package com.zx._12_算法.排序;

import com.zx._12_算法.Arrs.IAS;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import lombok.extern.slf4j.Slf4j;


/**
 * https://www.runoob.com/w3cnote/bucket-sort.html
 * 是在计数排序基础
 */
@Slf4j
public class Sort8_桶排序 implements IAS {

    @Override
    public void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 获取最大与最小
        int min = arr[0];
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        int buckCount = buck(max - min) + 1;
        List<List<Integer>> buck = new ArrayList<>(buckCount);
        for (int i = 0; i < buckCount; i++) {
            buck.add(new ArrayList<>());
        }

        for (int i = 0; i < arr.length; i++) {
            int k = buck(arr[i] - min);
            buck.get(k).add(arr[i]);
        }

        int idx = 0;
        for (int i = 0; i < buck.size(); i++) {
            List<Integer> barr = buck.get(i);
            if (barr == null || barr.size() == 0) {
                continue;
            }
            // 选择一种排序算法
            Collections.sort(barr);
            for (int j = 0; j < barr.size(); j++) {
                arr[idx] = barr.get(j);
                idx++;
            }
        }
    }

    public int buck(int i) {
        return (int) Math.floor(i / 5);
    }

}
